package 中等.模拟;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/diagonal-traverse/
 */
public class 对角线遍历_498 {

    public static void main(String[] args) {

        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        // 1,2,4,7,5,3,6,8,9
        System.out.println(Arrays.toString(findDiagonalOrder(mat)));

    }

    /**
     * 广度优先搜索
     *
     * @param mat
     * @return
     */
    public static int[] findDiagonalOrder(int[][] mat) {
        int rows = mat.length, columns = mat[0].length;
        int[] ans = new int[rows * columns];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{0, 0});

        int index = 0;
        boolean fromHead = false;

        while (!queue.isEmpty()) {
            int size = queue.size();
            int tIdx = index;
            if (!fromHead) tIdx = index + size - 1;
            index += size;
            boolean begin = true;
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                int row = cur[0];
                int column = cur[1];
                ans[tIdx] = mat[row][column];
                if (column + 1 < columns && begin) {
                    queue.addLast(new int[]{row, column + 1});
                }
                if (row + 1 < rows) {
                    queue.addLast(new int[]{row + 1, column});
                }
                if (fromHead) {
                    tIdx++;
                } else {
                    tIdx--;
                }
                begin = false;
            }

            fromHead = !fromHead;
        }
        return ans;
    }

}
